# 给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
#
#  求在该柱状图中，能够勾勒出来的矩形的最大面积。
#
#
#
#
#
#  以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为 [2,1,5,6,2,3]。
#
#
#
#
#
#  图中阴影部分为所能勾勒出的最大矩形面积，其面积为 10 个单位。
#
#
#
#  示例:
#
#  输入: [2,1,5,6,2,3]
# 输出: 10
#  Related Topics 栈 数组
#  👍 886 👎 0


# leetcode submit region begin(Prohibit modification and deletion)
class Solution(object):
    def largestRectangleArea(self, heights):
        """
        :type heights: List[int]
        :rtype: int
        其实就是单调栈的运用。可以这么思考，如果遇到的柱子比之前的柱子高，
        那么入栈，反之这时候停下来计算之前每根柱子能够形成打最大矩形，因为是递增的性质，
        所以可以都算出来。但是栈里保存的是 下标，这个需要额外注意
        """

        stack = []
        max_area = 0

        for i in range(0, len(heights)):
            # 栈空或者当前柱子比栈顶的高，即可入栈
            if len(stack) == 0 or heights[i] > heights[stack[- 1]]:
                stack.append(i)
            else:
                # 把比当前柱子高的柱子全部出栈（包括相同高度），同时计算 最大举行高度
                top = 0
                while len(stack) > 0 and heights[i] <= heights[stack[- 1]]:
                    top = stack[- 1]
                    stack.pop()
                    width = i - top
                    max_area = max(max_area, width * heights[top])
                heights[top] = heights[i]
                stack.append(top)

        # 栈内还有元素
        while len(stack) != 0:
            j = stack.pop()
            width = len(heights) if len(stack) == 0 else len(heights) - j
            max_area = max(max_area, width * heights[j])

        return max_area
    # leetcode submit region end(Prohibit modification and deletion)


# [5,1,2,4]
# [1,2,2]
# [2,1,2]
print(Solution().largestRectangleArea([1, 2, 2]))

arr = [1,2,3]

arr.reverse()
